{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Distance to Type a Word Using Two Fingers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二指输入的的最小距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/11/leetcode_keyboard.png\" /></p>\n",
    "\n",
    "<p>二指输入法定制键盘在 <strong>X-Y</strong> 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如字母&nbsp;<strong>A</strong>&nbsp;位于坐标&nbsp;<strong>(0,0)</strong>，字母&nbsp;<strong>B</strong>&nbsp;位于坐标&nbsp;<strong>(0,1)</strong>，字母&nbsp;<strong>P</strong>&nbsp;位于坐标&nbsp;<strong>(2,3)</strong>&nbsp;且字母 <strong>Z</strong>&nbsp;位于坐标&nbsp;<strong>(4,1)</strong>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个待输入字符串&nbsp;<code>word</code>，请你计算并返回在仅使用两根手指的情况下，键入该字符串需要的最小移动总距离。</p>\n",
    "\n",
    "<p>坐标<code>&nbsp;<strong>(x<sub>1</sub>,y<sub>1</sub>)</strong> </code>和 <code><strong>(x<sub>2</sub>,y<sub>2</sub>)</strong></code> 之间的 <strong>距离</strong> 是&nbsp;<code><strong>|x<sub>1</sub> - x<sub>2</sub>| + |y<sub>1</sub> - y<sub>2</sub>|</strong></code>。&nbsp;</p>\n",
    "\n",
    "<p><strong>注意</strong>，两根手指的起始位置是零代价的，不计入移动总距离。你的两根手指的起始位置也不必从首字母或者前两个字母开始。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word = \"CAKE\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释： \n",
    "</strong>使用两根手指输入 \"CAKE\" 的最佳方案之一是： \n",
    "手指 1 在字母 'C' 上 -&gt; 移动距离 = 0 \n",
    "手指 1 在字母 'A' 上 -&gt; 移动距离 = 从字母 'C' 到字母 'A' 的距离 = 2 \n",
    "手指 2 在字母 'K' 上 -&gt; 移动距离 = 0 \n",
    "手指 2 在字母 'E' 上 -&gt; 移动距离 = 从字母 'K' 到字母 'E' 的距离  = 1 \n",
    "总距离 = 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word = \"HAPPY\"\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释： </strong>\n",
    "使用两根手指输入 \"HAPPY\" 的最佳方案之一是：\n",
    "手指 1 在字母 'H' 上 -&gt; 移动距离 = 0\n",
    "手指 1 在字母 'A' 上 -&gt; 移动距离 = 从字母 'H' 到字母 'A' 的距离 = 2\n",
    "手指 2 在字母 'P' 上 -&gt; 移动距离 = 0\n",
    "手指 2 在字母 'P' 上 -&gt; 移动距离 = 从字母 'P' 到字母 'P' 的距离 = 0\n",
    "手指 1 在字母 'Y' 上 -&gt; 移动距离 = 从字母 'A' 到字母 'Y' 的距离 = 4\n",
    "总距离 = 6\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= word.length &lt;= 300</code></li>\n",
    "\t<li>每个 <code>word[i]</code>&nbsp;都是一个大写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-distance-to-type-a-word-using-two-fingers](https://leetcode.cn/problems/minimum-distance-to-type-a-word-using-two-fingers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-distance-to-type-a-word-using-two-fingers](https://leetcode.cn/problems/minimum-distance-to-type-a-word-using-two-fingers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"CAKE\"', '\"HAPPY\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        ORDA = ord(\"A\")\n",
    "        dist =  lambda x,y:abs(x//6-y//6)  +  abs(x%6-y%6)\n",
    "        n = len(word)\n",
    "        dp = [0] * 26 \n",
    "        i = 1\n",
    "        for char in word[1:]:\n",
    "            cur, prev = ord(char) - ORDA, ord(word[i-1]) - ORDA\n",
    "            ndp = [inf]* 26\n",
    "            d = dist(cur, prev)\n",
    "            for j in range(26):\n",
    "                ndp[j] = min(ndp[j], dp[j] + d )\n",
    "                if prev == j:\n",
    "                    for k in range(26):\n",
    "                        d0 = dist(k, cur)\n",
    "                        ndp[prev] = min(ndp[prev], dp[k] + d0)\n",
    "            dp = ndp\n",
    "            i += 1\n",
    "        return min(dp)\n",
    "\n",
    "           \n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dis(a, b):\n",
    "            return abs(a//6 - b//6) + abs(a%6 - b%6)\n",
    "        \n",
    "        A = [ord(c) - 65 for c in word]\n",
    "        dp = [0] * 26\n",
    "        for i in range(n - 1):\n",
    "            b, c = A[i], A[i + 1]\n",
    "            dp[b] = max(dp[a] + dis(b, c) - dis(a, c) for a in range(26))\n",
    "        return sum(dis(A[i], A[i + 1]) for i in range(n - 1)) - max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        wordlst = [ord(c)-65 for c in word]\n",
    "        n = len(wordlst)\n",
    "        BIG = 2 ** 30\n",
    "        dp = [[BIG] * 26 for _ in range(26)]\n",
    "        for i in range(26):\n",
    "            dp[i][wordlst[0]] = 0\n",
    "            dp[wordlst[0]][i] = 0\n",
    "\n",
    "        def getDistance(p, q):\n",
    "            x1, y1 = divmod(p, 6)\n",
    "            x2, y2 = divmod(q, 6)\n",
    "            return abs(x1 - x2) + abs(y1 - y2)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp2 = [[BIG] * 26 for _ in range(26)]\n",
    "            cur, prev = wordlst[i], wordlst[i - 1]\n",
    "            d = getDistance(prev, cur)\n",
    "            for j in range(26):\n",
    "                dp2[cur][j] = dp[prev][j] + d\n",
    "                dp2[j][cur] = dp[j][prev] + d\n",
    "            j = prev\n",
    "            v1 = dp2[cur][j]\n",
    "            v2 = dp2[j][cur]\n",
    "            for k in range(26):\n",
    "                d0 = getDistance(k, cur)\n",
    "                v1 = min(v1, dp[k][j] + d0)\n",
    "                v2 = min(v2, dp[j][k] + d0)\n",
    "            dp2[cur][j] = v1\n",
    "            dp2[j][cur] = v2\n",
    "            dp = dp2\n",
    "        ans = min(min(dp[x]) for x in range(26))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        wordlst = [ord(c)-65 for c in word]\n",
    "        n = len(wordlst)\n",
    "        BIG = 2 ** 30\n",
    "        dp = [[BIG] * 26 for _ in range(26)]\n",
    "        for i in range(26):\n",
    "            dp[i][wordlst[0]] = 0\n",
    "            dp[wordlst[0]][i] = 0\n",
    "\n",
    "        def getDistance(p, q):\n",
    "            x1, y1 = divmod(p, 6)\n",
    "            x2, y2 = divmod(q, 6)\n",
    "            return abs(x1 - x2) + abs(y1 - y2)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp2 = [[BIG] * 26 for _ in range(26)]\n",
    "            cur, prev = wordlst[i], wordlst[i - 1]\n",
    "            d = getDistance(prev, cur)\n",
    "            for j in range(26):\n",
    "                dp2[cur][j] = min(dp2[cur][j], dp[prev][j] + d)\n",
    "                dp2[j][cur] = min(dp2[j][cur], dp[j][prev] + d)\n",
    "            j = prev\n",
    "            for k in range(26):\n",
    "                d0 = getDistance(k, cur)\n",
    "                dp2[cur][j] = min(dp2[cur][j], dp[k][j] + d0)\n",
    "                dp2[j][cur] = min(dp2[j][cur], dp[j][k] + d0)\n",
    "            dp = dp2\n",
    "        ans = min(min(dp[x]) for x in range(26))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        ORDA = ord(\"A\")\n",
    "        dist =  lambda x,y:abs(x//6-y//6)  +  abs(x%6-y%6)\n",
    "        n = len(word)\n",
    "        dp = [0] * 26 \n",
    "        for i, char in enumerate(word[1:]):\n",
    "            cur, prev = ord(char) - ORDA, ord(word[i]) - ORDA\n",
    "            ndp = [inf]* 26\n",
    "            d = dist(cur, prev)\n",
    "            for j in range(26):\n",
    "                ndp[j] = min(ndp[j], dp[j] + d )\n",
    "                if prev == j:\n",
    "                    for k in range(26):\n",
    "                        d0 = dist(k, cur)\n",
    "                        ndp[prev] = min(ndp[prev], dp[k] + d0)\n",
    "            dp = ndp\n",
    "        return min(dp)\n",
    "\n",
    "           \n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        def dis(x, y):\n",
    "            if x == 26 or y == 26:\n",
    "                return 0\n",
    "            return abs(x // 6 - y // 6) + abs(x % 6 - y % 6)\n",
    "\n",
    "        A = ord('A')\n",
    "        d = [0] * 26\n",
    "\n",
    "        for i in range(1, len(word)):\n",
    "            cur, prev = ord(word[i]) - A, ord(word[i - 1]) - A\n",
    "            n = [d[j] + dis(cur, prev) for j in range(26)]\n",
    "            n[prev] = min([d[j] + dis(cur, j) for j in range(26)])\n",
    "            d = n\n",
    "\n",
    "        return min(d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        wordlst = [ord(c)-65 for c in word]\n",
    "        n = len(wordlst)\n",
    "        BIG = 2 ** 30\n",
    "        dp = [[BIG] * 26 for _ in range(26)]\n",
    "        for i in range(26):\n",
    "            dp[i][wordlst[0]] = 0\n",
    "            dp[wordlst[0]][i] = 0\n",
    "\n",
    "        def getDistance(p, q):\n",
    "            x1, y1 = divmod(p, 6)\n",
    "            x2, y2 = divmod(q, 6)\n",
    "            return abs(x1 - x2) + abs(y1 - y2)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp2 = [[BIG] * 26 for _ in range(26)]\n",
    "            cur, prev = wordlst[i], wordlst[i - 1]\n",
    "            d = getDistance(prev, cur)\n",
    "            for j in range(26):\n",
    "                dp2[cur][j] = dp[prev][j] + d\n",
    "                dp2[j][cur] = dp[j][prev] + d\n",
    "            j = prev\n",
    "            for k in range(26):\n",
    "                d0 = getDistance(k, cur)\n",
    "                dp2[cur][j] = min(dp2[cur][j], dp[k][j] + d0)\n",
    "                dp2[j][cur] = min(dp2[j][cur], dp[j][k] + d0)\n",
    "            dp = dp2\n",
    "        ans = min(min(dp[x]) for x in range(26))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        ORDA = ord(\"A\")\n",
    "        dist =  lambda x,y:abs(x//6-y//6)  +  abs(x%6-y%6)\n",
    "        n = len(word)\n",
    "        dp = [[inf] * 26 for _ in range(26)]\n",
    "        for i in range(26):\n",
    "            dp[i][ord(word[0]) - ORDA] = 0\n",
    "            dp[ord(word[0])-ORDA][i] = 0\n",
    "        i  =1\n",
    "        for char in word[1:]:\n",
    "            cur, prev = ord(char) - ORDA, ord(word[i-1]) - ORDA\n",
    "            ndp = [[inf]* 26  for _ in range(26)]\n",
    "            d = dist(cur, prev)\n",
    "            for j in range(26):\n",
    "                # 左手从prev 移到当前\n",
    "                ndp[cur][j] = min(ndp[cur][j], dp[prev][j] + d )\n",
    "                # 右手从prev 移到当前\n",
    "                ndp[j][cur] = min(ndp[j][cur], dp[j][prev] + d )\n",
    "                if prev == j:\n",
    "                    for k in range(26):\n",
    "                        d0 = dist(k, cur)\n",
    "                        ndp[cur][prev] = min(ndp[cur][prev], dp[k][prev] + d0 )\n",
    "                        ndp[prev][cur] = min(ndp[prev][cur], dp[prev][k] + d0 )\n",
    "            i += 1\n",
    "            dp = ndp\n",
    "        return min(min(dp[x]) for x in range(26))\n",
    "\n",
    "           \n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getDistance(p, q):\n",
    "    x1, y1 = divmod(p, 6)\n",
    "    x2, y2 = divmod(q, 6)\n",
    "    return abs(x1 - x2) + abs(y1 - y2)\n",
    "def tryadd(c1,c2,val,state):\n",
    "    v = state.get((c1,c2), val+1)\n",
    "    if v > val:\n",
    "        state[(c1,c2)] = val\n",
    "def try1(c1,c2,val,c,state):\n",
    "    d = getDistance(c1,c)\n",
    "    tryadd(c,c2,val+d,state)\n",
    "def try2(c1,c2,val,c,state):\n",
    "    if c2 == -1:\n",
    "        tryadd(c1,c,val,state)\n",
    "        return\n",
    "    d = getDistance(c2,c)\n",
    "    tryadd(c1,c,val+d,state)\n",
    "class State:\n",
    "    def __init__(self):\n",
    "        self.laststate = []\n",
    "    def set_red(self, c):\n",
    "        self.laststate.append((c,-1, 0))\n",
    "    def try_(self, c):\n",
    "        newstate = {}\n",
    "        for c1,c2,val in self.laststate:\n",
    "            try1(c1,c2,val,c,newstate)\n",
    "            try2(c1,c2,val,c,newstate)\n",
    "        self.laststate.clear()\n",
    "        self.laststate = [(a,b,c) for (a,b),c in newstate.items()]\n",
    "    def get_min_dist(self):\n",
    "        v0 = self.laststate[0][2]\n",
    "        for _,_,v in self.laststate:\n",
    "            v0 = min(v0, v)\n",
    "        return v0\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        wordlst = [ord(c)-ord('A') for c in word]\n",
    "        n = len(word)\n",
    "        state = State()\n",
    "        c0 = wordlst[0]\n",
    "        # 红队取 c0, 蓝队取空\n",
    "        state.set_red(c0)\n",
    "        for c in wordlst[1:]:\n",
    "            state.try_(c)\n",
    "        return state.get_min_dist()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        dp = [0] * 26 \n",
    "        def get_dis(v1, v2):\n",
    "            return abs(v1 // 6 - v2 // 6) + abs(v1 % 6 - v2 % 6)\n",
    "        for i in range(1, n):\n",
    "            pre = ord(word[i - 1]) - ord('A')\n",
    "            cur = ord(word[i]) - ord('A')\n",
    "            new = [float('inf')] * 26 \n",
    "            for val in range(26):\n",
    "                new[val] = min(new[val], dp[val] + get_dis(pre, cur))\n",
    "                new[pre] = min(new[pre], dp[val] + get_dis(val, cur))\n",
    "            dp = new \n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getDistance(p,q):\n",
    "    x1,y1 = divmod(p,6)\n",
    "    x2,y2 = divmod(q,6)\n",
    "    return abs(x1-x2) + abs(y1-y2)\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        wordlst = [ord(c)-ord('A') for c in word]\n",
    "        n = len(word)\n",
    "        BIG = 2**30\n",
    "        dp = [[BIG]*26 for _ in range(26)]\n",
    "        c0 = wordlst[0]\n",
    "        for i in range(26):\n",
    "            dp[i][c0] = 0\n",
    "            dp[c0][i] = 0\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            dp2 = [[BIG] * 26 for _ in range(26)]\n",
    "            cur,prev = wordlst[i],wordlst[i-1]\n",
    "            d = getDistance(prev,cur)\n",
    "            for j in range(26):\n",
    "                dp2[cur][j] = dp[prev][j] + d\n",
    "                dp2[j][cur] = dp[j][prev] + d\n",
    "            \n",
    "            v1 = dp2[cur][prev]\n",
    "            v2 = dp2[prev][cur]\n",
    "            for k in range(26):\n",
    "                d0 = getDistance(k,cur)\n",
    "                v1 = min(v1,dp[k][prev]+d0)\n",
    "                v2 = min(v2,dp[prev][k]+d0)\n",
    "            dp2[cur][prev] = v1\n",
    "            dp2[prev][cur] = v2\n",
    "\n",
    "            dp = dp2\n",
    "        ans = min(min(dp[x]) for x in range(26))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        def getDistance(c1, c2):\n",
    "            x1, y1 = c1 // 6, c1 % 6\n",
    "            x2, y2 = c2 // 6, c2 % 6\n",
    "            return abs(x1 - x2) + abs(y1 - y2)\n",
    "\n",
    "        L = len(word)\n",
    "        BIG = 2 ** 30\n",
    "        dp = [[0] * 26] + [[BIG] * 26 for n in range(L-1)]\n",
    "\n",
    "        for n in range(1, L):\n",
    "            cur, prev = ord(word[n]) - 65, ord(word[n-1]) - 65\n",
    "            cur_dist = getDistance(cur, prev)\n",
    "            for i in range(26):\n",
    "                dp[n][i] = min(dp[n-1][i] + cur_dist, dp[n][i])\n",
    "                if i == prev:\n",
    "                    for k in range(26):\n",
    "                        dp[n][i] = min(dp[n][i], dp[n-1][k]+getDistance(k, cur))\n",
    "                     \n",
    "        return min(dp[L - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        BIG = 99999\n",
    "\n",
    "        def dis(x, y):\n",
    "            if x == 26 or y == 26:\n",
    "                return 0\n",
    "            return abs(x // 6 - y // 6) + abs(x % 6 - y % 6)\n",
    "\n",
    "        d = [[[BIG] * 27 for _ in range(27)] for __ in range(2)]\n",
    "        d[1][26][26] = 0\n",
    "        for i, c in enumerate(word):\n",
    "            t = ord(c) - ord('A')\n",
    "            for dx in range(27):\n",
    "                for dy in range(27):\n",
    "                    d[i % 2][dx][dy] = BIG\n",
    "            for dx in range(27):\n",
    "                for dy in range(27):\n",
    "                    d[i % 2][t][dy] = min(d[i % 2][t][dy], d[(i + 1) % 2][dx][dy] + dis(dx, t))\n",
    "                    d[i % 2][dx][t] = min(d[i % 2][dx][t], d[(i + 1) % 2][dx][dy] + dis(dy, t))\n",
    "        m = BIG\n",
    "        for i in range(26):\n",
    "            for j in range(26):\n",
    "                m = min(m, d[(len(word) + 1) % 2][i][j])\n",
    "        return m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getDistance(p,q):\n",
    "    x1,y1 = divmod(p,6)\n",
    "    x2,y2 = divmod(q,6)\n",
    "    return abs(x1-x2)+abs(y1-y2)\n",
    "def tryadd(c1,c2,val,state):\n",
    "    v = state.get((c1,c2),val+1)\n",
    "    if v > val:\n",
    "        state[(c1,c2)] = val\n",
    "def try1(c1,c2,val,c,state):\n",
    "    d = getDistance(c1,c)\n",
    "    tryadd(c,c2,val+d,state)\n",
    "def try2(c1,c2,val,c,state):\n",
    "    if c2 == -1:\n",
    "        tryadd(c1,c,val,state)\n",
    "        return\n",
    "    d = getDistance(c2,c)\n",
    "    tryadd(c1,c,val+d,state)\n",
    "class State:\n",
    "    def __init__(self):\n",
    "        self.laststate = []\n",
    "    def set_red(self,c):\n",
    "        self.laststate.append((c,-1,0))\n",
    "    def try_(self,c):\n",
    "        newstate = {}\n",
    "        for c1,c2,val in self.laststate:\n",
    "            try1(c1,c2,val,c,newstate)\n",
    "            try2(c1,c2,val,c,newstate)\n",
    "        self.laststate.clear()\n",
    "        self.laststate = [(a,b,c) for (a,b),c in newstate.items()]\n",
    "\n",
    "    def get_min_dist(self):\n",
    "        v0 = self.laststate[0][2]\n",
    "        print(v0)\n",
    "        for _,_,v in self.laststate:\n",
    "\n",
    "            v0 = min(v0,v)\n",
    "        return v0\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self,word:str)->int:\n",
    "        wordlst = [ord(c)-ord('A') for c in word]#输入字符串 word 中的每个字符转换为其在大写字母表中的位置（偏移量）\n",
    "        n = len(word)\n",
    "        state = State()\n",
    "\n",
    "        c0 = wordlst[0]\n",
    "        #红队取c0，蓝队取空\n",
    "        state.set_red(c0)\n",
    "        for c in wordlst[1:]:\n",
    "            state.try_(c)\n",
    "        return state.get_min_dist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getDistance(p,q):\n",
    "    x1,y1 = divmod(p,6)\n",
    "    x2,y2 = divmod(q,6)\n",
    "    return abs(x1-x2)+abs(y1-y2)\n",
    "def tryadd(c1,c2,val,state):\n",
    "    v = state.get((c1,c2),val+1)\n",
    "    if v > val:\n",
    "        state[(c1,c2)] = val\n",
    "def try1(c1,c2,val,c,state):\n",
    "    d = getDistance(c1,c)\n",
    "    tryadd(c,c2,val+d,state)\n",
    "def try2(c1,c2,val,c,state):\n",
    "    if c2 == -1:\n",
    "        tryadd(c1,c,val,state)\n",
    "        return\n",
    "    d = getDistance(c2,c)\n",
    "    tryadd(c1,c,val+d,state)\n",
    "class State:\n",
    "    def __init__(self):\n",
    "        self.laststate = []\n",
    "    def set_red(self,c):\n",
    "        self.laststate.append((c,-1,0))\n",
    "    def try_(self,c):\n",
    "        newstate = {}\n",
    "        for c1,c2,val in self.laststate:\n",
    "            try1(c1,c2,val,c,newstate)\n",
    "            try2(c1,c2,val,c,newstate)\n",
    "        self.laststate.clear()\n",
    "        self.laststate = [(a,b,c) for (a,b),c in newstate.items()]\n",
    "\n",
    "    def get_min_dist(self):\n",
    "        v0 = self.laststate[0][2]\n",
    "        print(v0)\n",
    "        for _,_,v in self.laststate:\n",
    "\n",
    "            v0 = min(v0,v)\n",
    "        return v0\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self,word:str)->int:\n",
    "        wordlst = [ord(c)-ord('A') for c in word]\n",
    "        n = len(word)\n",
    "        state = State()\n",
    "\n",
    "        c0 = wordlst[0]\n",
    "        #红队取c0，蓝队取空\n",
    "        state.set_red(c0)\n",
    "        for c in wordlst[1:]:\n",
    "            state.try_(c)\n",
    "        return state.get_min_dist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        x, y = 0, 0\n",
    "        coor = {}\n",
    "        for i in range(26):\n",
    "            coor[i] = (x, y)\n",
    "            y += 1\n",
    "            if y == 6:\n",
    "                y = 0\n",
    "                x += 1\n",
    "        distance = {}\n",
    "        for i in range(26):\n",
    "            for j in range(26):\n",
    "                x1, y1 = coor[i]\n",
    "                x2, y2 = coor[j]\n",
    "                distance[(i, j)] = abs(x1-x2) + abs(y1-y2)\n",
    "        #for i in range(26):\n",
    "            #distance[(27, i)] = 0\n",
    "        #记录到第i个字母的情况下，手指j在当前位置，手指1-j在位置k\n",
    "        #dp[i][2][27]\n",
    "        n = len(word)\n",
    "        dp = [[[10**9] * 26 for i in range(2)] for j in range(n)]\n",
    "        #print(len(dp), len(dp[0]), len(dp[0][0]))\n",
    "        #print(distance)\n",
    "        for i in range(26):\n",
    "            dp[0][0][i] = 0\n",
    "            dp[0][1][i] = 0\n",
    "        word = [ord(x) - ord('A') for x in word]\n",
    "        for i in range(1, len(word)):\n",
    "            for j in range(2):\n",
    "                for k in range(26):\n",
    "                    #j在word[i] 1-j在k\n",
    "                    dp[i][j][k] = dp[i-1][j][k] + distance[(word[i-1], word[i])]#用和上一次按键一样的手\n",
    "                    #上一次是1-j按的建，这次又移动的是j，所以上一次1-j就必须在k才行\n",
    "                    if word[i-1] == k:\n",
    "                        for L in range(26):\n",
    "                            dp[i][j][k] = min(dp[i][j][k], dp[i-1][1-j][L] + distance[(L, word[i])])\n",
    "        return min(min(dp[-1][0]), min(dp[-1][1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        dis = [[0] * (n+1) for _ in range(n+1)]\n",
    "        def getd(ch1, ch2):\n",
    "            n1, n2 = ord(ch1) - ord('A'), ord(ch2) - ord('A')\n",
    "            x1, y1 = n1 % 6, n1 // 6\n",
    "            x2, y2 = n2 % 6, n2 // 6\n",
    "            return (abs(x1 - x2) + abs(y1 - y2))\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i+1, n+1):\n",
    "                dis[i][j] = getd(word[j-1], word[i-1])\n",
    "        # print(dis)\n",
    "        dp = [[0] * (n+1) for _ in range(n+1)]\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(i-1):\n",
    "                dp[i][j] = dp[i-1][j] + dis[i-1][i]\n",
    "            dp[i][i-1] = dp[i-1][0] \n",
    "            for k in range(i-1):\n",
    "                dp[i][i-1] = min(dp[i][i-1], dp[i-1][k] + dis[k][i])\n",
    "        # print(dp)\n",
    "        return min(dp[n][:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        BIG = 2**30\n",
    "        dp = [[[BIG] * 26 for x in range(26)] for y in range(n)]\n",
    "        for i in range(26):\n",
    "            dp[0][i][ord(word[0]) - 65] = 0\n",
    "            dp[0][ord(word[0]) - 65][i] = 0\n",
    "    \n",
    "        def getDistance(p, q):\n",
    "            x1, y1 = p // 6, p % 6\n",
    "            x2, y2 = q // 6, q % 6\n",
    "            return abs(x1 - x2) + abs(y1 - y2)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            cur, prev = ord(word[i]) - 65, ord(word[i - 1]) - 65\n",
    "            d = getDistance(prev, cur)\n",
    "            for j in range(26):\n",
    "                dp[i][cur][j] = min(dp[i][cur][j], dp[i - 1][prev][j] + d)\n",
    "                dp[i][j][cur] = min(dp[i][j][cur], dp[i - 1][j][prev] + d)\n",
    "                if prev == j:\n",
    "                    for k in range(26):\n",
    "                        d0 = getDistance(k, cur)\n",
    "                        dp[i][cur][j] = min(dp[i][cur][j], dp[i - 1][k][j] + d0)\n",
    "                        dp[i][j][cur] = min(dp[i][j][cur], dp[i - 1][j][k] + d0)\n",
    "        \n",
    "        ans = min(min(dp[n - 1][x]) for x in range(26))\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        BIG = 2**30\n",
    "        dp = [[[BIG] * 26 for x in range(26)] for y in range(n)]\n",
    "        for i in range(26):\n",
    "            dp[0][i][ord(word[0]) - 65] = 0\n",
    "            dp[0][ord(word[0]) - 65][i] = 0\n",
    "    \n",
    "        def getDistance(p, q):\n",
    "            x1, y1 = p // 6, p % 6\n",
    "            x2, y2 = q // 6, q % 6\n",
    "            return abs(x1 - x2) + abs(y1 - y2)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            cur, prev = ord(word[i]) - 65, ord(word[i - 1]) - 65\n",
    "            d = getDistance(prev, cur)\n",
    "            for j in range(26):\n",
    "                dp[i][cur][j] = min(dp[i][cur][j], dp[i - 1][prev][j] + d)\n",
    "                dp[i][j][cur] = min(dp[i][j][cur], dp[i - 1][j][prev] + d)\n",
    "                if prev == j:\n",
    "                    for k in range(26):\n",
    "                        d0 = getDistance(k, cur)\n",
    "                        dp[i][cur][j] = min(dp[i][cur][j], dp[i - 1][k][j] + d0)\n",
    "                        dp[i][j][cur] = min(dp[i][j][cur], dp[i - 1][j][k] + d0)\n",
    "        \n",
    "        ans = min(min(dp[n - 1][x]) for x in range(26))\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        dp = [[[float(\"inf\")]* 26 for _ in range(26)] for _ in range(n)]\n",
    "        for i in range(26):\n",
    "            #左右手分别放在起始点，另一只手随便放\n",
    "            dp[0][i][ord(word[0])-65]=0\n",
    "            dp[0][ord(word[0])-65][i]=0\n",
    "        def dist(i1,i2):\n",
    "            x1,y1 = i1//6,i1%6\n",
    "            x2,y2 = i2//6,i2%6\n",
    "            return abs(x1-x2)+abs(y1-y2)\n",
    "        for i in range(1,n):\n",
    "            cur,pre = ord(word[i])-65,ord(word[i-1])-65\n",
    "            d = dist(pre,cur)\n",
    "            for j in range(26):\n",
    "                dp[i][cur][j] = min(dp[i][cur][j],dp[i-1][pre][j]+d)\n",
    "                dp[i][j][cur] = min(dp[i][j][cur],dp[i-1][j][pre]+d)\n",
    "                if j==pre:\n",
    "                    for k in range(26):\n",
    "                        d1 = dist(k,cur)\n",
    "                        dp[i][cur][j] = min(dp[i][cur][j],dp[i-1][k][pre]+d1)\n",
    "                        dp[i][j][cur] = min(dp[i][j][cur],dp[i-1][pre][k]+d1)\n",
    "        return min(min(dp[n-1][i]) for i in range(26))\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        def calc_dis(i, j):\n",
    "            if i < 0 or j < 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return abs(pos[i][0] - pos[j][0]) + abs(pos[i][1] - pos[j][1])\n",
    "        pos = []\n",
    "        for i in range(26):\n",
    "            pos.append([i // 6, i % 6])\n",
    "        f = [[[len(word) * 100] * 27 for _ in range(27)] for _ in range(len(word) + 1)]\n",
    "        f[0][-1][ord(word[0]) - ord('A')] = f[0][ord(word[0]) - ord('A')][-1] = 0\n",
    "        for i, char in enumerate(word[1:]):\n",
    "            p = ord(char) - ord('A')\n",
    "            prev = ord(word[i]) - ord('A')\n",
    "            for j in range(-1, 26):\n",
    "                f[i + 1][prev][p] = min(f[i + 1][prev][p], f[i][prev][j] + calc_dis(j, p))\n",
    "                f[i + 1][p][prev] = min(f[i + 1][p][prev], f[i][j][prev] + calc_dis(j, p))\n",
    "                f[i + 1][p][j] = min(f[i + 1][p][j], f[i][prev][j] + calc_dis(prev, p))\n",
    "                f[i + 1][j][p] = min(f[i + 1][j][p], f[i][j][prev] + calc_dis(prev, p))\n",
    "        \n",
    "\n",
    "        return min(min(f[len(word) - 1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        BIG = 2**30\n",
    "        dp = [[[BIG] * 26 for x in range(26)] for y in range(n)]\n",
    "        for i in range(26):\n",
    "            dp[0][i][ord(word[0]) - 65] = 0\n",
    "            dp[0][ord(word[0]) - 65][i] = 0\n",
    "    \n",
    "        def getDistance(p, q):\n",
    "            x1, y1 = p // 6, p % 6\n",
    "            x2, y2 = q // 6, q % 6\n",
    "            return abs(x1 - x2) + abs(y1 - y2)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            cur, prev = ord(word[i]) - 65, ord(word[i - 1]) - 65\n",
    "            d = getDistance(prev, cur)\n",
    "            for j in range(26):\n",
    "                dp[i][cur][j] = min(dp[i][cur][j], dp[i - 1][prev][j] + d)\n",
    "                dp[i][j][cur] = min(dp[i][j][cur], dp[i - 1][j][prev] + d)\n",
    "                if prev == j:\n",
    "                    for k in range(26):\n",
    "                        d0 = getDistance(k, cur)\n",
    "                        dp[i][cur][j] = min(dp[i][cur][j], dp[i - 1][k][j] + d0)\n",
    "                        dp[i][j][cur] = min(dp[i][j][cur], dp[i - 1][j][k] + d0)\n",
    "        \n",
    "        ans = min(min(dp[n - 1][x]) for x in range(26))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        ORDA = ord(\"A\")\n",
    "        dist =  lambda x,y:abs(x//6-y//6)  +  abs(x%6-y%6)\n",
    "        n = len(word)\n",
    "        dp = [[[inf] * 26 for _ in range(26)] for __ in range(n)]\n",
    "        for i in range(26):\n",
    "            dp[0][i][ord(word[0]) - ORDA] = 0\n",
    "            dp[0][ord(word[0])-ORDA][i] = 0\n",
    "        i  =1\n",
    "        for char in word[1:]:\n",
    "            cur, prev = ord(char) - ORDA, ord(word[i-1]) - ORDA\n",
    "            d = dist(cur, prev)\n",
    "            for j in range(26):\n",
    "                # 左手从prev 移到当前\n",
    "                dp[i][cur][j] = min(dp[i][cur][j], dp[i-1][prev][j] + d )\n",
    "                # 右手从prev 移到当前\n",
    "                dp[i][j][cur] = min(dp[i][j][cur], dp[i-1][j][prev] + d )\n",
    "                if prev == j:\n",
    "                    for k in range(26):\n",
    "                        d0 = dist(k, cur)\n",
    "                        dp[i][cur][prev] = min(dp[i][cur][prev], dp[i-1][k][prev] + d0 )\n",
    "                        dp[i][prev][cur] = min(dp[i][prev][cur], dp[i-1][prev][k] + d0 )\n",
    "            i += 1\n",
    "        return min(min(dp[n-1][x]) for x in range(26))\n",
    "\n",
    "           \n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        row_len = 6\n",
    "        coord = dict()\n",
    "        c, i, j = \"A\", 0, 0\n",
    "        while c != \"Z\":\n",
    "            coord[c] = (i, j)\n",
    "            if j == 5:\n",
    "                i += 1\n",
    "                j = 0\n",
    "            else:\n",
    "                j += 1\n",
    "            c = chr(ord(c) + 1)\n",
    "        coord[c] = (i, j)\n",
    "        def distance(c1, c2):\n",
    "            if c1 == \"#\" or c2 == \"#\":\n",
    "                return 0\n",
    "            coord1_x, coord1_y = coord[c1]\n",
    "            coord2_x, coord2_y = coord[c2]\n",
    "            return abs(coord1_x - coord2_x) + abs(coord1_y - coord2_y)\n",
    "        @cache\n",
    "        def dfs(c1, i):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            c2 = word[i + 1] if i < len(word) - 1 else \"#\"\n",
    "            res1 = distance(c1, word[i]) + dfs(c2, i - 1)\n",
    "            res2 = distance(c2, word[i]) + dfs(c1, i - 1)\n",
    "            return min(res1, res2)\n",
    "        return dfs(\"#\", len(word) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        d = [\n",
    "            (0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5),\n",
    "            (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5),\n",
    "            (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5),\n",
    "            (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5),\n",
    "            (4, 0), (4, 1)\n",
    "            ]\n",
    "        n = len(word)\n",
    "        dp = [[[0]*(26) for _ in range(26)] for _ in range(n+1)]\n",
    "        for now in range(n-1, -1, -1):\n",
    "            k = ord(word[now]) - ord('A')\n",
    "            for i in range(26):\n",
    "                for j in range(26):\n",
    "                    dp[now][i][j] = min(\n",
    "                        abs(d[i][0]-d[k][0]) + abs(d[i][1]-d[k][1]) + dp[now+1][k][j],\n",
    "                        abs(d[j][0]-d[k][0]) + abs(d[j][1]-d[k][1]) + dp[now+1][i][k]\n",
    "                    )\n",
    "        res = inf\n",
    "        for a in range(26):\n",
    "            for b in range(a):\n",
    "                res = min(res, dp[0][a][b])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        d = [\n",
    "            (0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5),\n",
    "            (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5),\n",
    "            (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5),\n",
    "            (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5),\n",
    "            (4, 0), (4, 1)\n",
    "            ]\n",
    "        se = set()\n",
    "        for e in word:\n",
    "            se.add(ord(e) - ord('A'))\n",
    "        n = len(word)\n",
    "        dp = [[[0]*(26) for _ in range(26)] for _ in range(n+1)]\n",
    "        for now in range(n-1, -1, -1):\n",
    "            k = ord(word[now]) - ord('A')\n",
    "            for i in se:\n",
    "                for j in se:\n",
    "                    dp[now][i][j] = min(\n",
    "                        abs(d[i][0]-d[k][0]) + abs(d[i][1]-d[k][1]) + dp[now+1][k][j],\n",
    "                        abs(d[j][0]-d[k][0]) + abs(d[j][1]-d[k][1]) + dp[now+1][i][k]\n",
    "                    )\n",
    "        res = inf\n",
    "        a = ord(word[0]) - ord('A')\n",
    "        for b in se:\n",
    "            res = min(res, dp[0][a][b])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        board = [[\"A\", \"B\", \"C\", \"D\", \"E\", \"F\"],\n",
    "                    [\"G\", \"H\", \"I\", \"J\", \"K\", \"L\"],\n",
    "                    [\"M\", \"N\", \"O\", \"P\", \"Q\", \"R\"],\n",
    "                    [\"S\", \"T\", \"U\", \"V\", \"W\", \"X\"],\n",
    "                    [\"Y\", \"Z\", \" \", \" \", \" \", \" \"]]\n",
    "        location = {}\n",
    "        for i in range(5):\n",
    "            for j in range(6):\n",
    "                if board[i][j] != \" \":\n",
    "                    location[board[i][j]] = (i, j)\n",
    "        @lru_cache(None)\n",
    "        def dfs(c1, c2, i):\n",
    "            if i == len(word):\n",
    "                return 0\n",
    "            pos = location[word[i]]\n",
    "            pos1 = location[c1]\n",
    "            pos2 = location[c2]\n",
    "            k1 = abs(pos1[0] - pos[0]) + abs(pos1[1] - pos[1])\n",
    "            k2 = abs(pos2[0] - pos[0]) + abs(pos2[1] - pos[1])\n",
    "            return min(k1 + dfs(min(word[i], c2), max(word[i], c2), i + 1), k2 + dfs(min(word[i], c1), max(word[i], c1), i + 1))\n",
    "        ans = inf\n",
    "        for i in range(26):\n",
    "            ans = min(ans, dfs(min(word[0], chr(ord(\"A\") + i)), max(word[0], chr(ord(\"A\") + i)), 1))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        def calc_dis(i, j):\n",
    "            if i < 0 or j < 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return abs(pos[i][0] - pos[j][0]) + abs(pos[i][1] - pos[j][1])\n",
    "        pos = []\n",
    "        for i in range(26):\n",
    "            pos.append([i // 6, i % 6])\n",
    "        f = [[[len(word) * 100 for _ in range(27)] for _ in range(27)] for _ in range(len(word) + 1)]\n",
    "        f[0][-1][ord(word[0]) - ord('A')] = f[0][ord(word[0]) - ord('A')][-1] = 0\n",
    "        for i, char in enumerate(word[1:]):\n",
    "            p = ord(char) - ord('A')\n",
    "            prev = ord(word[i]) - ord('A')\n",
    "            for j in range(-1, 26):\n",
    "                f[i + 1][prev][p] = min(f[i + 1][prev][p], f[i][prev][j] + calc_dis(j, p))\n",
    "                f[i + 1][p][prev] = min(f[i + 1][p][prev], f[i][j][prev] + calc_dis(j, p))\n",
    "                f[i + 1][p][j] = min(f[i + 1][p][j], f[i][prev][j] + calc_dis(prev, p))\n",
    "                f[i + 1][j][p] = min(f[i + 1][j][p], f[i][j][prev] + calc_dis(prev, p))\n",
    "        \n",
    "\n",
    "        return min(min(f[len(word) - 1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        def calc_dis(i, j):\n",
    "            if i < 0 or j < 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return abs(pos[i][0] - pos[j][0]) + abs(pos[i][1] - pos[j][1])\n",
    "        pos = []\n",
    "        for i in range(26):\n",
    "            pos.append([i // 6, i % 6])\n",
    "        f = [[[len(word) * 100 for _ in range(27)] for _ in range(27)] for _ in range(len(word) + 1)]\n",
    "        f[0][-1][-1] = 0\n",
    "        for i, char in enumerate(word):\n",
    "            p = ord(char) - ord('A')\n",
    "            for j in range(-1, 26):\n",
    "                for k in range(-1, 26):\n",
    "                    f[i + 1][p][k] = min(f[i + 1][p][k], f[i][j][k] + calc_dis(j, p))\n",
    "                    f[i + 1][j][p] = min(f[i + 1][j][p], f[i][j][k] + calc_dis(k, p))\n",
    "        \n",
    "        return min(min(f[len(word)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        row_len = 6\n",
    "        coord = dict()\n",
    "        c, i, j = \"A\", 0, 0\n",
    "        while c != \"Z\":\n",
    "            coord[c] = (i, j)\n",
    "            if j == 5:\n",
    "                i += 1\n",
    "                j = 0\n",
    "            else:\n",
    "                j += 1\n",
    "            c = chr(ord(c) + 1)\n",
    "        coord[c] = (i, j)\n",
    "        def distance(c1, c2):\n",
    "            if c1 == \"#\" or c2 == \"#\":\n",
    "                return 0\n",
    "            coord1_x, coord1_y = coord[c1]\n",
    "            coord2_x, coord2_y = coord[c2]\n",
    "            return abs(coord1_x - coord2_x) + abs(coord1_y - coord2_y)\n",
    "        @cache\n",
    "        def dfs(c1, c2, i):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            res1 = distance(c1, word[i]) + dfs(word[i], c2, i - 1)\n",
    "            res2 = distance(c2, word[i]) + dfs(c1, word[i], i - 1)\n",
    "            return min(res1, res2)\n",
    "        return dfs(\"#\", \"#\", len(word) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        d = {}\n",
    "        for i in range(26):\n",
    "            c = chr(ord('A')+i)\n",
    "            d[c] = (i//6, i%6)\n",
    "\n",
    "        def dist(a,b):\n",
    "            if a==' ':\n",
    "                return 0\n",
    "            return abs(d[a][0]-d[b][0])+abs(d[a][1]-d[b][1])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, pre1, pre2):\n",
    "            if i==len(word):\n",
    "                return 0\n",
    "            use1 = dist(pre1,word[i]) + dfs(i+1, word[i], pre2)\n",
    "            use2 = dist(pre2,word[i]) + dfs(i+1, pre1, word[i])\n",
    "            # print(i,pre1,pre2,use1,use2)\n",
    "            return min(use1,use2)\n",
    "        \n",
    "        return dfs(0, ' ', ' ')\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        \n",
    "        dct = dict()\n",
    "        for i in range(26):\n",
    "            dct[chr(i+ord(\"A\"))] = [i//6, i % 6]\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, p1, p2):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            x, y = dct[word[i]]\n",
    "            cost1 = 0 if not p1 else abs(x-dct[p1][0]) +abs(y-dct[p1][1])\n",
    "            res1 = dfs(i+1, word[i], p2) + cost1\n",
    "\n",
    "            x, y = dct[word[i]]\n",
    "            cost2 = 0 if not p2 else abs(x - dct[p2][0]) + abs(y - dct[p2][1])\n",
    "            res2 = dfs(i + 1, p1, word[i]) + cost2\n",
    "            return res1 if res1 < res2 else res2\n",
    "        \n",
    "        n = len(word)\n",
    "        return dfs(0, \"\", \"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        def calc(now, nxt):\n",
    "            if now == 30:\n",
    "                return 0\n",
    "            x, y = now // 6, now % 6\n",
    "            nx, ny = nxt // 6, nxt % 6\n",
    "            return abs(x - nx) + abs(y - ny)\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, l, r):\n",
    "            if i == len(word):\n",
    "                return 0\n",
    "            nxt = ord(word[i]) - ord('A')\n",
    "            return min(dfs(i + 1, nxt, r) + calc(l, nxt), dfs(i + 1, l, nxt) + calc(r, nxt))\n",
    "        return dfs(0, 30, 30)\n",
    "\n",
    "# 作者：评论区某大神。\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "\n",
    "        def cal(now, nxt):\n",
    "            if now == 26:\n",
    "                return 0\n",
    "            sx, sy = now // 6, now % 6\n",
    "            tx, ty = nxt // 6, nxt % 6\n",
    "            return abs(sx - tx) + abs(sy - ty)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, l, r):\n",
    "            if i == len(word):\n",
    "                return 0\n",
    "            nxt = ord(word[i]) - ord('A')\n",
    "            return min(dfs(i + 1, nxt, r) + cal(l, nxt), dfs(i + 1, l, nxt) + cal(r, nxt))\n",
    "\n",
    "        return dfs(0, 26, 26)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        def calc(now, nxt):\n",
    "            if now == 30:\n",
    "                return 0\n",
    "            x, y = now // 6, now % 6\n",
    "            nx, ny = nxt // 6, nxt % 6\n",
    "            return abs(x - nx) + abs(y - ny)\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, l, r):\n",
    "            if i == len(word):\n",
    "                return 0\n",
    "            nxt = ord(word[i]) - ord('A')\n",
    "            return min(dfs(i + 1, nxt, r) + calc(l, nxt), dfs(i + 1, l, nxt) + calc(r, nxt))\n",
    "        return dfs(0, 30, 30)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        def calc(now, nxt):\n",
    "            if now == 30:\n",
    "                return 0\n",
    "            x, y = now // 6, now % 6\n",
    "            nx, ny = nxt // 6, nxt % 6\n",
    "            return abs(x - nx) + abs(y - ny)\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, l, r):\n",
    "            if i == len(word):\n",
    "                return 0\n",
    "            nxt = ord(word[i]) - ord('A')\n",
    "            return min(dfs(i + 1, nxt, r) + calc(l, nxt), dfs(i + 1, l, nxt) + calc(r, nxt))\n",
    "        return dfs(0, 30, 30)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        def calc(now, nxt):\n",
    "            if now == 30:\n",
    "                return 0\n",
    "            x, y = now // 6, now % 6\n",
    "            nx, ny = nxt // 6, nxt % 6\n",
    "            return abs(x - nx) + abs(y - ny)\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, l, r):\n",
    "            if i == len(word):\n",
    "                return 0\n",
    "            nxt = ord(word[i]) - ord('A')\n",
    "            # ord返回一个字符的Unicode码点（整数表示），相当于字符与整数的一一对应，一个工具。\n",
    "            # dfs(i+1, nxt, r)相当于第i步用了左手，此时左手已经在了第i步的nxt的位置；dfs(i+1, l, nxt)相当于第i步用右手，此时右手已经在了第i步的nxt的位置。\n",
    "            return min(dfs(i + 1, nxt, r) + calc(l, nxt), dfs(i + 1, l, nxt) + calc(r, nxt))\n",
    "        return dfs(0, 30, 30)\n",
    "\n",
    "# 作者：评论区某大神。\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        # dp\n",
    "        d = defaultdict(list)\n",
    "        for i in range(4):\n",
    "            for j in range(6):\n",
    "                ch = chr(ord('A') + i * 6 + j)\n",
    "                d[ch] = [i, j]\n",
    "        d['Y'] = [4, 0]\n",
    "        d['Z'] = [4, 1]\n",
    "        def cost(ch1, ch2): # 从ch1移动到ch2的代价\n",
    "            if ch1 == '': return 0\n",
    "            x1, y1 = d[ch1]\n",
    "            x2, y2 = d[ch2]\n",
    "            return abs(x1 - x2) + abs(y1 - y2)\n",
    "        n = len(word)\n",
    "        # 26 * 26 * 300\n",
    "        @cache\n",
    "        def dfs(ch1, ch2, cur):\n",
    "            if cur == n:\n",
    "                return 0\n",
    "            res = inf\n",
    "            nxt = word[cur]\n",
    "            res = min(res, dfs(nxt, ch2, cur + 1) + cost(ch1, nxt))\n",
    "            res = min(res, dfs(ch1, nxt, cur + 1) + cost(ch2, nxt))\n",
    "            return res\n",
    "\n",
    "        \n",
    "        return dfs('', '', 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        def calc(now, nxt):\n",
    "            if now == 31:\n",
    "                return 0\n",
    "            x, y = now // 6, now % 6\n",
    "            nx, ny = nxt // 6, nxt % 6\n",
    "            return abs(x - nx) + abs(y - ny)\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, l, r):\n",
    "            if i == len(word):\n",
    "                return 0\n",
    "            nxt = ord(word[i]) - ord('A')\n",
    "            return min(dfs(i + 1, nxt, r) + calc(l, nxt), dfs(i + 1, l, nxt) + calc(r, nxt))\n",
    "        return dfs(0, 31, 31)\n",
    "\n",
    "# 作者：评论区某大神。\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        def calc(now, nxt):\n",
    "            if now == 30:\n",
    "                return 0\n",
    "            x, y = now // 6, now % 6\n",
    "            nx, ny = nxt // 6, nxt % 6\n",
    "            return abs(x - nx) + abs(y - ny)\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, l, r):\n",
    "            if i == len(word):\n",
    "                return 0\n",
    "            nxt = ord(word[i]) - ord('A')\n",
    "            return min(dfs(i + 1, nxt, r) + calc(l, nxt), dfs(i + 1, l, nxt) + calc(r, nxt))\n",
    "        return dfs(0, 30, 30)\n",
    "\n",
    "# 作者：评论区某大神。\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        def get_dist(a, b):\n",
    "            a, b = ord(a) - 65, ord(b) - 65\n",
    "            ax, ay = a // 6, a % 6\n",
    "            bx, by = b // 6, b % 6\n",
    "            return abs(ax - bx) + abs(ay - by)\n",
    "        n = len(word)\n",
    "        @cache\n",
    "        def dfs(i, l, r):\n",
    "            if i == n: return 0\n",
    "            res = inf\n",
    "            if l == '1':\n",
    "                res = min(res, dfs(i + 1, word[i], r))\n",
    "            elif l != '1':\n",
    "                res = min(res, get_dist(word[i], l) + dfs(i + 1, word[i], r))\n",
    "            if r == '1':\n",
    "                res = min(res, dfs(i + 1, l, word[i]))\n",
    "            elif r != '1':\n",
    "                res = min(res, get_dist(word[i], r) + dfs(i + 1, l, word[i]))\n",
    "            return res\n",
    "        return dfs(0, '1', '1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        def calc(now, nxt):\n",
    "            if now == 30:\n",
    "                return 0\n",
    "            x, y = now // 6, now % 6\n",
    "            nx, ny = nxt // 6, nxt % 6\n",
    "            return abs(x - nx) + abs(y - ny)\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, l, r):\n",
    "            if i == len(word):\n",
    "                return 0\n",
    "            nxt = ord(word[i]) - ord('A')\n",
    "            # ord返回一个字符的Unicode码点（整数表示），相当于字符与整数的一一对应，一个工具。\n",
    "            # dfs(i+1, nxt, r)相当于第i步用了左手，此时左手已经在了第i步的nxt的位置；dfs(i+1, l, nxt)相当于第i步用右手，此时右手已经在了第i步的nxt的位置。\n",
    "            return min(dfs(i + 1, nxt, r) + calc(l, nxt), dfs(i + 1, l, nxt) + calc(r, nxt))\n",
    "        return dfs(0, 30, 30)\n",
    "\n",
    "# 作者：评论区某大神。\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "jp=[]\n",
    "x,y=0,0\n",
    "for _ in range(26):\n",
    "    jp.append((x,y))\n",
    "    y+=1\n",
    "    if y==6:\n",
    "        x+=1\n",
    "        y=0\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        n=len(word)\n",
    "        @cache\n",
    "        def dfs(i,l,r):\n",
    "            if i==n:return 0\n",
    "            t=ord(word[i])-ord('A')\n",
    "            return min(abs(jp[t][0]-jp[l][0])+abs(jp[t][1]-jp[l][1])+dfs(i+1,t,r),abs(jp[t][0]-jp[r][0])+abs(jp[t][1]-jp[r][1])+dfs(i+1,l,t))\n",
    "        res=10**10\n",
    "        l=ord(word[0])-ord('A')\n",
    "        for r in range(26):\n",
    "            res=min(res,dfs(1,l,r))\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "\n",
    "        # 两个字母的距离\n",
    "        @cache\n",
    "        def d(a,b):\n",
    "            if a==0 or b==0:\n",
    "                return 0\n",
    "            a = ord(a)-ord('A')\n",
    "            b = ord(b)-ord('A')\n",
    "            x1,y1 = a//6,a%6\n",
    "            x2,y2 = b//6,b%6\n",
    "            return abs(x1-x2)+abs(y1-y2)\n",
    "\n",
    "        @cache\n",
    "        def f(l, r, indx):\n",
    "            if indx == n:\n",
    "                return 0\n",
    "\n",
    "            l1,l2 = d(l,word[indx]), d(r,word[indx])\n",
    "            \n",
    "            res1 = l1 + f(word[indx], r, indx+1)\n",
    "            res2 = l2 + f(l, word[indx], indx+1)\n",
    "            return min(res1, res2)\n",
    "        \n",
    "        return f(0,0,0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        n = len(word)\n",
    "        ans = inf\n",
    "        \n",
    "        @cache\n",
    "        def dfs(x1 :int, y1:int, x2: int, y2: int, u: int) -> int:\n",
    "            if (u == n):\n",
    "                return 0\n",
    "            t = ord(word[u]) - ord('A')\n",
    "            x, y = t // 6, t % 6\n",
    "            d1 = abs(x1 - x) + abs(y1 - y) + dfs(x, y, x2, y2, u + 1)\n",
    "            d2 = abs(x2 - x) + abs(y2 - y) + dfs(x1, y1, x, y, u + 1)\n",
    "            return min(d1, d2)\n",
    "\n",
    "        t1 = ord(word[0]) - ord('A')\n",
    "        x1, y1 = t1 // 6, t1 % 6\n",
    "\n",
    "        for i in range(n):\n",
    "            t2 = ord(word[i]) - ord('A')\n",
    "            x2, y2 = t2 // 6, t2 % 6\n",
    "            ans = min(ans, dfs(x1, y1, x2, y2, 0))\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "        d = [\n",
    "            (0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5),\n",
    "            (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5),\n",
    "            (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5),\n",
    "            (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5),\n",
    "            (4, 0), (4, 1)\n",
    "            ]\n",
    "        n = len(word)\n",
    "        @cache\n",
    "        def fun(now, i, j):\n",
    "            if n == now:\n",
    "                return 0\n",
    "            k = ord(word[now]) - ord('A')\n",
    "            return min(\n",
    "                abs(d[i][0]-d[k][0]) + abs(d[i][1]-d[k][1]) + fun(now+1, k, j),\n",
    "                abs(d[j][0]-d[k][0]) + abs(d[j][1]-d[k][1]) + fun(now+1, i, k)\n",
    "            )\n",
    "        res = inf\n",
    "        for i in range(26):\n",
    "            for j in range(i):\n",
    "                res = min(res, fun(0, i, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDistance(self, word: str) -> int:\n",
    "      n = len(word)\n",
    "\n",
    "      def dis(i: int, j: int) -> int:\n",
    "         return abs(i // 6 - j // 6) + abs(i % 6 - j % 6)\n",
    "\n",
    "      @cache\n",
    "      def dfs(i: int, p1: int, p2: int) -> int:\n",
    "         if i == n:\n",
    "            return 0\n",
    "         return min(dfs(i + 1, ord(word[i]) - ord('A'), p2) + dis(ord(word[i]) - ord('A'), p1),\n",
    "                    dfs(i + 1, p1,ord(word[i]) - ord('A')) + dis(ord(word[i]) - ord('A'), p2))\n",
    "      res = inf\n",
    "      for i in range(26):\n",
    "         for j in range(26):\n",
    "            res = min(res, dfs(0, i, j))\n",
    "      return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
